package leetcode019;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
 * 19. 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 */
public class Study019 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode current = head;
        Map<Integer, ListNode> map = new HashMap<>();
        int index = 0;
        while (current != null) {
            index++;
            map.put(index, current);
            current = current.next;
        }
        //最后一个节点
        if (n == 1) {
            if (index > 1) {
                map.get(index - 1).next = null;
                return head;
            } else {
                return null;
            }
        } else if (n == index) {//第一个节点
            if (index > 1) {
                return head.next;
            } else {
                return null;
            }
        } else {
            map.get(index - n).next = map.get(index - n + 2);
            return head;
        }
    }



    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode root = new ListNode(0);
        root.next = head;
        ListNode prevN = root;

        ListNode current = head;
        for (int i = 1; i <= n; i++) {
            current = current.next;
        }
        while (current != null) {
            prevN = prevN.next;
            current = current.next;
        }

        prevN.next = prevN.next.next;
        return root.next;

    }


}
